The present invention relates to a method of generating a spatial representation of a three-dimensional solid object and to a solid modelling system for performing such a method.
Objects may be represented in a graphics processing system using various techniques. One which is particularly suitable for representing solid objects is "Constructive Solid Geometry" (CSG). In accordance with this technique a three-dimensional (3-D) solid object is represented by a functional definition identifying the set of points which lie within the object. Typically, the object is defined by a Boolean function which returns a "true" if applied to a point within the object and returns a "false" otherwise. This technique contrasts with, for example, line drawing techniques where the edges and surfaces of an object are defined rather than its volume.
The functional definition of an object effectively defines the set of points which make up the object. The functional definition of a sphere, for example, defines the set of points lying within a given radius of a center point. Composite objects are defined by combining the functional definitions of constituent basic objects, or "primitives", e.g. spheres, infinite planes, infinite cylinders. The functional definition of a dumb-bell, for example, would comprise the functional definition of each of two spheres at different positions, the functional definition of an infinite cylinder whose axis passes through the centers of the spheres and the functional definitions of two planar half-spaces which truncate the cylinder at the spheres, the functional definitions of the spheres, the cylinder and the planar half-spaces being combined using set union and intersect operators (i.e. using set theory principles). Primitives can also be combined using other combinational operators such as set subtracting operators to define, for example, a composite object with a cut-out or hole. In this way hollow composite objects can be defined by subtracting a smaller object from a larger one. Such composite objects are still "solid" within the meaning of this application because the individual object definitions which make up the composite object are solid.
A composite object formed from primitives can be structured in a number of ways. However it is usual to use a tree structure with the composite object being defined at the root of the tree, the primitives being defined at the leaves and operators being defined at nodes in the tree to identify the combinational operations to be performed to construct the object from the primitives and/or sub-objects defined at lower-order nodes in the tree.
The range of shapes which can be defined in this way is, in practice, dependent on the set of primitives chosen. In many prior systems, objects are constructed only from planar half-spaces. A planar half-space is a functional definition of an infinite object which exists on one side of a plane. The functional definition of a cube is, for example, defined by combining the functional definitions of six half-spaces using the set intersection operator. Other systems have also been implemented using cylinders, spheres, tori, ellipsoids and even helices.
Some shapes still cannot be defined exactly, however, using these techniques. Examples are an egg shape (which is essentially a tapered sphere), a helix with a box-shaped cross section, or a double-coiled helix. These have conventionally been approximated, often with great difficulty, from simpler shapes, normally planar half-spaces.